package com.zhanghp.class034;

/**
 * 复制带随机指针的链表<br/>
 * 测试链接 : https://leetcode.cn/problems/copy-list-with-random-pointer/<br/>
 *
 * @author zhanghp
 * @since 2024/4/11 9:55
 */
public class Code03_CopyListWithRandomPointer {


    static class Node {
        public int val;
        public Node next;
        public Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    static class Solution {
        public Node copyRandomList(Node head) {
            if (head == null) {
                return head;
            }
            // 增加复制节点
            // a -> b -> c
            // a -> a' -> b -> b' -> c -> c'
            Node cur = head, next;
            while (cur != null) {
                next = cur.next;
                cur.next = new Node(cur.val);
                cur.next.next = next;
                cur = next;
            }
            // 利用上面新老节点的结构关系，设置每一个新节点的random指针
            cur = head;
            Node copy = null;
            while (cur != null) {
                copy = cur.next;
                copy.random = cur.random == null ? null : cur.random.next;
                cur = cur.next.next;
            }
            // 新老链表分离 : 老链表重新连在一起，新链表重新连在一起
            Node ans = head.next;
            cur = head;
            while (cur != null) {
                // =新老链表下一节点设值=
                // 下一组头节点
                next = cur.next.next;
                // 当前组复制节点
                copy = cur.next;
                // 老节点重新设值下一个连接节点
                cur.next = next;
                // 新节点重新设值下一个连接节点
                copy.next = next != null ? next.next : null;
                cur = next;
            }
            // 返回新链表的头节点
            return ans;
        }
    }

    // ======================错误============================
    static class WrongSolution {
        /**
         * <p>wrong</p>
         * Random pointer of node with label 13 points to a node from the original list.
         * 复制出来的节点，random指向的是head的原始地址，而不是复制出来的地址
         *
         * @param head
         * @return
         */
        public Node wrongCopyRandomList(Node head) {
            if (head == null) {
                return head;
            }
            Node pre = null, ans = null, temp, cur = head;
            // a -> b -> c
            // a -> a' -> b -> b' -> c -> c'
            while (cur != null) {
                // 复制当前节点的值
                temp = cur.next;
                cur.next = new Node(cur.val);
                cur.next.next = temp;
                cur = temp;
            }
            while (head != null) {
                if (ans != null) {
                    ans.next = head.next;
                    ans = ans.next;
                } else {
                    ans = head.next;
                    pre = ans;
                }
                // 节点随机值处理
                head.next.random = head.random;
                // 下组节点
                temp = head.next.next;
                // 当前节点处理
                head.next = temp;

                head = temp;
            }
            return pre;
        }
    }


    static class Wrong2Solution {
        /**
         * Next pointer of node with label 7 from the original list was modified.
         * <p>
         * 原列表head的next指针更换了
         * <p>
         * random设值和head还原需分两步，否则random设值设的是original的node地址
         *
         * @param head
         * @return
         */
        public Node wrong2copyRandomList(Node head) {
            // boundary condition
            if (head == null) {
                return head;
            }
            Node ans = null, copyCur = null, originalCur = head, temp;
            // a -> b -> c
            // a -> a' -> b -> b' -> c -> c'
            while (originalCur != null) {
                temp = originalCur.next;
                originalCur.next = new Node(originalCur.val);
                originalCur.next.next = temp;
                originalCur = temp;
            }
            Node o2 = head;
            // 首个节点处理
            copyCur = o2.next;
            ans = copyCur;
            copyCur.random = o2.random == null ? null : o2.next.random;
            temp = o2.next.next;
            o2.next = temp;
            o2 = temp;
            // copy node
            while (o2 != null) {
                // todo
                copyCur.next = o2.next;
                copyCur.next.random = o2.random == null ? null : o2.next.random;
                temp = o2.next.next;
                o2.next = temp;
                o2 = temp;
                copyCur = copyCur.next;
            }
            return ans;
        }
    }
}
